package 面试经典150题.数组;

import java.util.Arrays;

/**
 * @author tmh
 * @date 2024/4/1 19:20
 * @description
 */
public class T88合并两个有序数组 {
    public static void main(String[] args) {
        int[] nums1 = {1, 2, 3, 0, 0, 0};
        int[] nums2 = new int[]{2, 5, 6};
        int m = 3;
        int n = 3;
        merge(nums1, m, nums2, n);
        System.out.println(Arrays.toString(nums1));
    }

    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int length = m + n;
        for (int i = n; i >= 1; i--) {
            nums1[length - 1] = nums2[i - 1];
            length--;
        }
        quickSort(nums1, 0, m + n - 1);
        System.out.println();

    }

    public static int partition(int[] array, int low, int high) {
        int pivot = array[high];
        int pointer = low;
        for (int i = low; i < high; i++) {
            if (array[i] <= pivot) {
                int temp = array[i];
                array[i] = array[pointer];
                array[pointer] = temp;
                //指针往后移动一位
                pointer++;
            }
        }
        //把指针指向的元素和pivot交换位置，得到的数组左面都是比pivot小的 右面都是比pivot大的
        int temp = array[high];
        array[high] = array[pointer];
        array[pointer] = temp;

        return pointer;
    }

    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int partition = partition(array, low, high);
            quickSort(array, low, partition - 1);
            quickSort(array, partition + 1, high);
        }
    }
}
